#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define STACKMAXSIZE 50

typedef int StackElemType;

typedef struct {
	StackElemType elem[STACKMAXSIZE];
	int top;
} SeqStack;

// 初始化
void InitSeqStack(SeqStack *S) {
	S->top = -1;
}

// 入栈
int PushStack(SeqStack *S, StackElemType e) {
	if (S->top >= STACKMAXSIZE - 1) {
		printf("栈满！\n");
		return 0;
	}
	S->elem[++S->top] = e;
	return 1;
}

// 出栈
int PopStack(SeqStack *S, StackElemType *e) {
	if (S->top < 0) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top--];
	return 1;
}

// 获取栈顶元素
int GetTop(SeqStack *S, StackElemType *e) {
	if (S->top < 0) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top];
	return 1;
}

// 运算符优先级比较
int Prior(char op) {
	switch (op) {
		case '#': return 0;
		case '(': return 1;
		case '+': case '-': return 3;
		case '*': case '/': return 5;
		case '^': return 7;
		default: return -1;
	}
}

// 表达式计算
int ExpEvaluation(char *str) {
	SeqStack numStack, opStack;
	InitSeqStack(&numStack);
	InitSeqStack(&opStack);
	PushStack(&opStack, '#');
	
	int i = 0, v1, v2, result, num, sign = 1;
	char op, c;
	
	// 处理换行符
	int len = strlen(str);
	if (len > 0 && str[len - 1] == '\n') {
		str[len - 1] = '\0';
	}
	
	while (str[i] != '\0') {
		if (str[i] == '-' && (i == 0 || str[i - 1] == '(')) {
			sign = -1;
			i++;
			continue;
		}
		if (str[i] >= '0' && str[i] <= '9') {
			num = 0;
			while (str[i] >= '0' && str[i] <= '9') {
				num = num * 10 + (str[i] - '0');
				i++;
			}
			PushStack(&numStack, num * sign);
			sign = 1;
			i--;
		} else if (str[i] == '(') {
			PushStack(&opStack, str[i]);
		} else if (str[i] == ')') {
			while (GetTop(&opStack, &op) == 1 && op != '(') {
				PopStack(&opStack, &op);
				PopStack(&numStack, &v2);
				PopStack(&numStack, &v1);
				switch (op) {
					case '+': result = v1 + v2; break;
					case '-': result = v1 - v2; break;
					case '*': result = v1 * v2; break;
					case '/': 
					if (v2 == 0) {
						printf("除数不能为 0！\n");
						exit(1);
					}
					result = v1 / v2; 
					break;
					case '^': 
					result = (int)round(pow(v1, v2)); 
					break;
					default: printf("未知操作符: %c\n", op); break;
				}
				PushStack(&numStack, result);
			}
			if (GetTop(&opStack, &op) == 1 && op == '(') {
				PopStack(&opStack, &op); // 弹出左括号
			}
		} else {
			StackElemType topOp;
			if (GetTop(&opStack, &topOp) == 1) {
				if (Prior(topOp) < Prior(str[i])) {
					PushStack(&opStack, str[i]);
				} else {
					PopStack(&opStack, &op);
					PopStack(&numStack, &v2);
					PopStack(&numStack, &v1);
					switch (op) {
						case '+': result = v1 + v2; break;
						case '-': result = v1 - v2; break;
						case '*': result = v1 * v2; break;
						case '/': 
						if (v2 == 0) {
							printf("除数不能为 0！\n");
							exit(1);
						}
						result = v1 / v2; 
						break;
						case '^': 
						result = (int)round(pow(v1, v2)); 
						break;
						default: printf("未知操作符: %c\n", op); break;
					}
					PushStack(&numStack, result);
				}
			} else {
				PushStack(&opStack, str[i]);
			}
		}
		i++;
	}
	
	// 处理剩余的运算符
	while (GetTop(&opStack, &op) == 1 && op != '#') {
		PopStack(&opStack, &op);
		PopStack(&numStack, &v2);
		PopStack(&numStack, &v1);
		switch (op) {
			case '+': result = v1 + v2; break;
			case '-': result = v1 - v2; break;
			case '*': result = v1 * v2; break;
			case '/': 
			if (v2 == 0) {
				printf("除数不能为 0！\n");
				exit(1);
			}
			result = v1 / v2; 
			break;
			case '^': 
			result = (int)round(pow(v1, v2)); 
			break;
			default: printf("未知操作符: %c\n", op); break;
		}
		PushStack(&numStack, result);
	}
	
	PopStack(&numStack, &result);
	return result;
}

int main() {
	int v;
	char str[80];
	printf("输入一个表达式，以#为结束！（输入括号时注意确保括号为英文状态下）\n");
	fgets(str, sizeof(str), stdin);
	v = ExpEvaluation(str);
	printf("该表达式的运算结果为：%d\n", v);
	return 0;
}
